package com.youxuit.youxu.suanfa;

import java.util.HashMap;
import java.util.Map;

public class Longest {
    public static void main(String[] args) {
        int i = lengthOfLongestSubstring("SDBJSDHSJHSJHDVSJHDVSBKBDRJHVAHVVAJDVAIAVUVVDJHAV");

    }

    //今日算法题：找出无重复字符的最长子串 参考题解
    public static int lengthOfLongestSubstring(String s) {
        //使用hash表记录元素和对应的索引，如果有重复值，则left移到重复索引处
        Map<Character,Integer> map = new HashMap<>();
        //定义左右指针, 连续区间长度即为right-lefht
        int left = -1;
        //定义最长区间
        int longest = 0;
        //遍历字符，右指针始终右移，左指针移动到重复元素位置
        for (int i = 0; i < s.length(); i++) {
            //map中是否包含当前元素，包含则重复，移动左指针
            if (map.containsKey(s.charAt(i))) {
                //max保证出现重复元素时left不会后退 比如abba这种情况
                left = Math.max(left, map.get(s.charAt(i)));
            }
            map.put(s.charAt(i), i);
            longest = Math.max(longest, i - left);
        }
        return longest;
    }
}
